package com.leetcode.tree.bst;

import com.leetcode.basic.ListNode;
import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/7/18 20:30
 */
public class SortedListToBST_109 {

    // 构造 BST
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 切断结点间联系，避免反复对整个链条进行遍历
        if (pre != null) pre.next = null;
        TreeNode node = new TreeNode(slow.val);
        // 根节点
        if (head == slow) return node;
        // 每次都是从头结点去找中间结点
        node.left = sortedListToBST(head);
        // slow.next 是右子树的头结点
        node.right = sortedListToBST(slow.next);
        return node;
    }

}
